package J.算法.动态规划;

import java.util.Arrays;

public class _322零钱兑换 {

    /**
     * 状态转移方程：
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {

        //初始化dp
        int[] dp = new int[amount+1];
        Arrays.fill(dp,-1);//这样就出错了 -1是有意义的状态值
        dp[0] = 0;

        //状态转移
        for (int i = 1; i <= amount ; i++) {
            for (int coin:coins){
                //转移条件
                if (i-coin>= 0 && dp[i-coin]!= -1){
                    dp[i] = Math.min(dp[i],dp[i-coin]+1);
                }
            }

        }


        return dp[amount];

    }

    /**
     * 递归法
     */

}
